//package Demo1_28;
//
///**
// * Created with IntelliJ IDEA.
// * Description:
// * User：Lenovo
// * Date:2025-01-28
// * Time:19:52
// */
//// 定义链表节点类
//class ListNode {
//    int val;
//    ListNode next;
//    ListNode(int x) {
//        val = x;
//        next = null;
//    }
//}
//
//public class PartitionList {
//    public ListNode partition(ListNode pHead, int x) {
//        // 创建两个虚拟头节点，分别用于存储小于 x 和大于等于 x 的节点
//        ListNode smallDummy = new ListNode(0);
//        ListNode largeDummy = new ListNode(0);
//        // 分别指向两个新链表的当前节点
//        ListNode smallTail = smallDummy;
//        ListNode largeTail = largeDummy;
//
//        // 遍历原链表
//        ListNode current = pHead;
//        while (current != null) {
//            if (current.val < x) {
//                // 如果当前节点的值小于 x，将其连接到 small 链表的尾部
//                smallTail.next = current;
//                smallTail = smallTail.next;
//            } else {
//                // 如果当前节点的值大于等于 x，将其连接到 large 链表的尾部
//                largeTail.next = current;
//                largeTail = largeTail.next;
//            }
//            // 移动到下一个节点
//            current = current.next;
//        }
//
//        // 断开 large 链表的尾部，防止出现循环
//        largeTail.next = null;
//        // 将 small 链表和 large 链表连接起来
//        smallTail.next = largeDummy.next;
//
//        // 返回重新排列后的链表的头节点
//        return smallDummy.next;
//    }
//
//    public static void main(String[] args) {
//        // 创建测试链表 1 -> 4 -> 3 -> 2 -> 5 -> 2
//        ListNode head = new ListNode(1);
//        head.next = new ListNode(4);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(2);
//        head.next.next.next.next = new ListNode(5);
//        head.next.next.next.next.next = new ListNode(2);
//
//        PartitionList solution = new PartitionList();
//        int x = 3;
//        // 调用 partition 方法进行重新排列
//        ListNode newHead = solution.partition(head, x);
//
//        // 打印重新排列后的链表
//        ListNode current = newHead;
//        while (current != null) {
//            System.out.print(current.val + " ");
//            current = current.next;
//        }
//    }
//}
